class Solution:
    def minimalSteps(self, maze) -> int:
        s = None
        t = None
        mSet = set()
        for i in range(len(maze)):
            for j in range(len(maze[i])):
                if maze[i][j] == 'S':
                    s = (i, j)
                elif maze[i][j] == 'T':
                    t = (i, j)
                elif maze[i][j] == 'M':
                    mSet.add((i, j))
        cachePointToPoint = {}
        cacheOneToOne = {}

        def oneToOne(x1, x2, needStone):
            if maze[x1[0]][x1[1]] == '#' or maze[x2[0]][x2[1]] == '#':
                return None
            if maze[x1[0]][x1[1]] == 'O' or maze[x2[0]][x2[1]] == 'O':
                needStone = False
            if (x1, x2, needStone) in cacheOneToOne:
                return cacheOneToOne[(x1, x2, needStone)]



        def pointToPoint(x1, x2, needStone):
            if x1 > x2:
                x1, x2 = x2, x1
            if (x1, x2, needStone) in cachePointToPoint:
                return cachePointToPoint[(x1, x2, needStone)]
            cachePointToPoint[(x1, x2, needStone)] = oneToOne(x1,x2,needStone)
            return cachePointToPoint[(x1, x2, needStone)]



if __name__ == "__main__":
    su = Solution()
    maze = []
    r = su.minimalSteps(maze)
    print(r)
